package srcInterviewPrep;

public final class LinkedListReverser
{
    public static final class Node
    {
        int data;
        Node next;

        public Node(int data)
        {
            this.data = data;
        }
    }

    public static Node ReverseList(Node node)
    {
        Node prev = null;
        Node cur = node;
        Node next;

        while (cur != null)
        {
            next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }

    public static Node ReverseRecursively(Node head)
    {
        if (head == null)
        {
            return null;
        }

        return ReverseRecursive(head);
    }

    private static Node ReverseRecursive(Node n)
    {
        if (n.next == null)
        {
            return n;
        }

        Node tail = n.next;
        Node head = ReverseRecursive(n.next);
        tail.next = n;
        n.next = null;

        return head;
    }
    
    public static Node ReverseTailRecursively(Node h)
    {
        return ReverseTailRecursively(null, h);
    }

    private static Node ReverseTailRecursively(Node prev, Node cur)
    {
        if (cur == null)
        {
            return prev;
        }
        
        Node temp = cur.next;
        cur.next = prev;
        return ReverseTailRecursively(cur, temp);
    }
}